#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 394. 字符串解码.py
@time: 2022/3/2 21:04
@desc: https://leetcode-cn.com/problems/decode-string/
> 给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像3a或2[4]的输入。

示例 1：
    输入：s = "3[a]2[bc]"
    输出："aaabcbc"
示例 2：
    输入：s = "3[a2[c]]"
    输出："accaccacc"

1. 如果当前的字符为数位，解析出一个数字（连续的多个数位）并进栈
2. 如果当前的字符为字母或者左括号，直接进栈
3. 如果当前的字符为右括号，开始出栈，一直到左括号出栈，出栈序列反转后拼接成一个字符串，此时取出栈顶的数字（此时栈顶一定是数字，想想为什么？），就是这个字符串应该出现的次数，我们根据这个次数和字符串构造出新的字符串并进栈

'''


class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        p = 0
        while p < len(s):
            # 如果是数字就找到完整的并入栈
            if '0' <= s[p] <= '9':
                ans = 0
                while '0' <= s[p] <= '9':
                    ans = ans * 10 + int(s[p])
                    p += 1
                stack.append(ans)

            # 如果是字母则入栈
            elif 'a' <= s[p] <= 'z' or 'A' <= s[p] <= 'Z' or s[p] == '[':
                stack.append(s[p])
                p += 1

            # 如果是右括号就出栈, 组成新字符再入栈
            elif s[p] == ']':
                tmp = []
                ele = stack.pop()
                while not ele == '[':
                    tmp.append(ele)
                    ele = stack.pop()

                # 逆序
                tmp = tmp[::-1]
                times = stack.pop()
                # 按times次数组合起来
                for i in range(times):
                    stack += list(tmp)
                p += 1

        return ''.join(stack)

if __name__ == '__main__':
    res = Solution().decodeString("abc3[cd]xyz")
    print(res)